#define _CRT_SECURE_NO_WARNINGS


//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (head == NULL)
//    {
//        return NULL;
//    }
//
//
//    struct ListNode* prev = NULL;
//    struct ListNode* cur = head;
//    struct ListNode* next = cur->next;
//
//
//    while (next)
//    {
//        cur->next = prev;
//        prev = cur;
//        cur = next;
//        next = next->next;
//    }
//
//
//    cur->next = prev;
//
//
//    return cur;
//}

//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    if (head == NULL)
//        return NULL;
//
//
//    struct ListNode* cur = head;
//    struct ListNode* next = cur->next;
//    while (cur != NULL && cur->val == val)
//    {
//        free(cur);
//        cur = next;
//        if (cur != NULL)
//            next = cur->next;
//    }
//
//
//    if (cur == next)
//        return NULL;
//
//
//    struct ListNode* NewHead = cur;
//    struct ListNode* prev = cur;
//
//
//    while (next)
//    {
//        if (cur->val == val)
//        {
//            free(cur);
//            prev->next = next;
//            cur = next;
//            next = cur->next;
//        }
//        else
//        {
//            prev = cur;
//            cur = next;
//            next = cur->next;
//        }
//    }
//
//
//    if (cur->val == val)
//    {
//        free(cur);
//        prev->next = NULL;
//    }
//
//
//    return NewHead;
//}




//struct ListNode* middleNode(struct ListNode* head)
//{
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//
//    return slow;
//}

//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
//{
//    struct ListNode* fast = pListHead;
//
//
//    int len = 0;
//    while (fast)
//    {
//        len++;
//        fast = fast->next;
//    }
//
//
//    if (k > len || k <= 0)
//        return NULL;
//
//
//    fast = pListHead;
//
//
//    while (k--)
//    {
//        fast = fast->next;
//    }
//
//
//    struct ListNode* slow = pListHead;
//
//
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//
//
//
//    return slow;
//}


//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    if (list1 == NULL)
//    {
//        return list2;
//    }
//
//    if (list2 == NULL)
//    {
//        return list1;
//    }
//
//    struct ListNode* cur1 = list1;
//    struct ListNode* cur2 = list2;
//
//    struct ListNode* head = NULL, * tail = NULL;
//
//    while (cur1 && cur2)
//    {
//        if (cur1->val < cur2->val)
//        {
//            if (head == NULL)
//            {
//                head = cur1;
//                tail = head;
//                cur1 = cur1->next;
//            }
//            else
//            {
//                tail->next = cur1;
//                tail = cur1;
//                cur1 = cur1->next;
//            }
//        }
//        else
//        {
//            if (head == NULL)
//            {
//                head = cur2;
//                tail = head;
//                cur2 = cur2->next;
//            }
//            else
//            {
//                tail->next = cur2;
//                tail = cur2;
//                cur2 = cur2->next;
//            }
//
//        }
//    }
//
//    while (cur1)
//    {
//        tail->next = cur1;
//        tail = cur1;
//        cur1 = cur1->next;
//    }
//
//    while (cur2)
//    {
//        tail->next = cur2;
//        tail = cur2;
//        cur2 = cur2->next;
//    }
//    tail->next = NULL;
//    return head;
//}


//#include <cstdlib>
//#include <new>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x)
//    {
//        ListNode* smallHead = (ListNode*)malloc(sizeof(ListNode));
//        smallHead->next = NULL;
//        ListNode* smalltail = smallHead;
//
//
//
//        ListNode* bigHead = (ListNode*)malloc(sizeof(ListNode));
//        bigHead->next = NULL;
//        ListNode* bigTail = bigHead;
//
//        ListNode* cur = pHead;
//
//
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                smalltail->next = cur;
//                smalltail = smalltail->next;
//            }
//            else
//            {
//                bigTail->next = cur;
//                bigTail = bigTail->next;
//            }
//            cur = cur->next;
//        }
//
//
//        bigTail->next = NULL;
//
//
//        ListNode* newHead = smallHead->next;
//        if (newHead == NULL)
//        {
//            newHead = bigHead->next;
//            free(smallHead);
//            free(bigHead);
//            return newHead;
//        }
//
//
//        smalltail->next = bigHead->next;
//
//
//        free(bigHead);
//        free(smallHead);
//
//
//
//        return newHead;
//    }
//};


//ListNode* reverse(ListNode* A)
//{
//
//    ListNode* cur = A;
//    ListNode* prev = NULL;
//    ListNode* next = cur->next;
//
//    while (next)
//    {
//        cur->next = prev;
//        prev = cur;
//        cur = next;
//        next = cur->next;
//    }
//    cur->next = prev;
//
//    return cur;
//}
//
//
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* A)
//    {
//        ListNode* fast = A;
//        ListNode* slow = A;
//
//        while (fast && fast->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//        }
//        ListNode* tail = reverse(slow);
//        ListNode* cur = A;
//        while (tail)
//        {
//            if (cur->val != tail->val)
//            {
//                return false;
//            }
//
//            cur = cur->next;
//            tail = tail->next;
//        }
//
//
//        return true;
//    }
//};

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

struct ListNode 
{
    int val;
    struct ListNode *next;
};
 

void Free(struct ListNode* begin, struct ListNode* end)
{
    struct ListNode* cur = begin;
    struct ListNode* next = cur->next;
    while (next != end)
    {
        free(cur);
        cur = next;
        next = next->next;
    }
    free(cur);
    free(next);
}

struct ListNode* deleteDuplication(struct ListNode* pHead)
{
    if (pHead == NULL)
        return NULL;

    struct ListNode* cur = pHead;
    struct ListNode* next = cur->next;

    while (cur != NULL && cur->val == next->val)
    {
        free(cur);
        cur = next;
        next = cur->next;
    }

    struct ListNode* head = cur;

    struct ListNode* same = next;
    struct ListNode* sameN = same->next;

    while (sameN)
    {

        if (same->val == sameN->val)
        {
            while (sameN->val == sameN->next->val)
            {
                sameN = sameN->next;
            }
            struct ListNode* sameNN = sameN->next;
            Free(same, sameN);
            cur->next = sameNN;
            same = cur->next;
            if (same)
                sameN = same->next;
        }
        else
        {
            same = sameN;
            if (same)
                sameN = sameN->next;
            cur = cur->next;
        }
    }

    return head;
}

int main()
{
    struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head7 = (struct ListNode*)malloc(sizeof(struct ListNode));
    head1->next = head2;
    head2->next = head3;
    head3->next = head4;
    head4->next = head5;
    head5->next = head6;
    head6->next = head7;
    head7->next = NULL;

    head1->val = 1;
    head2->val = 2;
    head3->val = 3;
    head4->val = 3;
    head5->val = 4;
    head6->val = 4;
    head7->val = 5;

    struct ListNode* phead = deleteDuplication(head1);

    free(head1);
    free(head2);
    free(head3);
    free(head4);
    free(head5);
    free(head6);
    free(head7);
    return 0;
}